The manufacturing process of today's integrated circuit (IC) design is very susceptible to defects. Each manufactured IC chip has to be subjected to a post-production test. Automatic test pattern generation (ATPG) systems test a chip by generating input assignments or test patterns that cause the outputs to be different if the chip is defective than if it is defect free. Traditional ATPG systems apply structural methods to generate test patterns. The structural methods use a data structure, such as a netlist, representing a circuit under test. To generate a test pattern, they assign values that cause a discrepancy at a faulted line (fault site) and then search for consistent values for all circuit lines such that the discrepancy is visible at a circuit output. Some notable structural methods are D-algorithm and FAN.
While widely being used, these structural methods have problems to cope with some hard-to-detect faults in today's complex circuit designs. The industry's demand for high fault coverage led to a renewed interest in nonstructural methods. Instead of performing a search on a data structure representing a circuit, some nonstructural methods, such as algebra methods, produce one or more equations describing all possible tests for a particular fault and then solve the resulting equation. One category of nonstructural methods are Boolean Satisfiability (SAT)-based methods. The SAT-based methods work on a Boolean formula in conjunctive normal form (CNF). The ATPG problem is transformed into a Boolean formula (or a SAT instance) first. Then, a SAT solver is used to solve the SAT instance. Many traditional SAT solvers are based on the original Davis-Putnam-Logemann-Loveland (DPLL) backtrack search algorithm. The algorithm performs a search process that traverses the space of 2n variable assignment until a satisfying assignment is found (the SAT instance is satisfiable) or all combinations have been exhausted (the SAT instance is unsatisfiable). A test pattern can be derived readily from the satisfying assignment.
Common to all ATPG methods is the preference of small test pattern sets. Small test pattern sets are important for reducing test storage requirements and test application time. Test compaction techniques are usually applied to reduce the size of test pattern sets. These techniques can be classified as static and dynamic. Static compaction techniques are applied to test pattern sets already generated to further reduce them. For example, reverse order fault simulation is usually used in a test generation procedure to drop test patterns that detect faults that are also detected by test patterns generated later in the test generation process. A more sophisticated static compaction method merges compatible test patterns into a single test pattern. Static compaction may also be enhanced by modifying bits in certain test patterns such that they would detect faults detected by other test patterns. The latter test patterns can then be removed from the test set without affecting the fault coverage. Dynamic compaction techniques are integrated into the test generation process, generally attempting to generate test patterns such that each one detects a large number of faults. For example, some dynamic compaction methods use unspecified input values in a test pattern for a given target fault to detect additional target faults. The same test pattern is thus evolved until no unspecified bits remain, or additional faults cannot be detected. These techniques are often dependent upon the fault ordering and are computationally intensive. Heuristics may be used to improve them. Some techniques combined static and dynamic method to generate compact test pattern sets.
Whether static, dynamic, or combined, traditional test compaction techniques usually use the input assignments (specified bits of a test pattern) for probing a fault as a constraint for compaction even if alternative assignments can be found and used for compaction. This may prevent minimal test sets from being found in some cases, and limit the effectiveness of the compaction techniques. FIG. 3 illustrates an example that explains the limitation. There are two faults in this example: F1 and F2 are two stuck-at 0 at the outputs of the gate G1 and G2, respectively. G1 is an XOR gate and G2 is an AND gate. To detect F1, it is sufficient to assign input A to 0 and input B to 1. However, a test pattern including this input assignment cannot detect F2 as the output of G2 would always be 0 no matter whether F2 is present in the circuit or not. On the other hand, F1 can also be probed by assigning input A and input B to 1 and 0, respectively. Under this input assignment, F2 can be probed simultaneously with F1 by assigning input C to 1. Therefore, if an ATPG system happens to derive a test vector with input assignment A=0 and B=1 first, it would be very difficult if not impossible for traditional test compaction techniques to generate a single test pattern for detecting both F1 and F2.